package com.jiang.daily.Q3347;

import java.util.Arrays;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/10/22 18:52
 */
class Solution {
    // public int maxFrequency(int[] nums, int k, int numOperations) {
    //     // 前缀和 pre[i] 表示数组中小于等于i-1的元素的个数
    //     // 遍历元素i 元素i的数量 x = pre[i+1]-pre[i]
    //     // num = pre[i+k]-pre[i-k]-x 表示元素i的约束范围内需要的操作数x+min(num,numOperations)表示限制操作次数下收束到i的频率
    //     // mx表示数组中元素最大值+1
    //     int mx = 0;
    //     for (int num : nums) {
    //         mx = Math.max(mx, num + 1);
    //     }
    //     // 前缀和数组 初始化时 pre[i]表示 元素i-1的计数
    //     int[] pre = new int[mx + 1];
    //     for (int num : nums) {
    //         pre[num + 1]++;
    //     }
    //     // 维护前缀和数组 此时 pre[i]表示数组中小于等于i-1的元素计数总数
    //     for (int i = 1; i <= mx; i++) {
    //         pre[i] += pre[i - 1];
    //     }
    //     int ans = 0;
    //     // 枚举收束到 i-1 的情况
    //     for (int i = 1; i <= mx; i++) {
    //         // 元素i-1出现的次数
    //         int x = pre[i] - pre[i - 1];
    //         // 数据范围 [i-1-k,i-1+k] 内的计数
    //         int v = pre[Math.min(mx, i + k)] - pre[Math.max(0, i - k - 1)];
    //         ans = Math.max(ans,Math.min(numOperations + x,v));
    //     }
    //     return ans;
    // }

    public int maxFrequency(int[] nums, int k, int numOperations) {
        Arrays.sort(nums);

        int n = nums.length;
        int ans = 0;
        int cnt = 0;
        int left = 0;
        int right = 0;
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            cnt++;
            // 循环直到连续相同段的末尾，这样可以统计出 x 的出现次数
            if (i < n - 1 && x == nums[i + 1]) {
                continue;
            }
            while (nums[left] < x - k) {
                left++;
            }
            while (right < n && nums[right] <= x + k) {
                right++;
            }
            ans = Math.max(ans, Math.min(right - left, cnt + numOperations));
            cnt = 0;
        }

        if (ans >= numOperations) {
            return ans;
        }

        left = 0;
        for (right = 0; right < n; right++) {
            int x = nums[right];
            while (nums[left] < x - k * 2) {
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return Math.min(ans, numOperations); // 最后和 numOperations 取最小值
    }
}
